Single Number

Posted on   |   In   |  

求出一个数组中的某个数只出现一次的所有题目

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
link
我们知道对于任意的整数x, x^x=0

1
2
3
4
5
6
7
8
9
10
int singleNumber(int* nums, int numsSize) {
    if(numsSize == 0|| nums == NULL)
        return 0;
    int ret = nums[0];
    
    for(int i = 1;  i < numsSize; i++){
        ret ^= nums[i];
    }
    return ret;
}

用hash

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, bool> ump;  
        for (int i = 0; i < nums.size(); i++)  
        {  
            if (!ump.count(nums[i])) ump[nums[i]] = true;  
            else ump.erase(nums[i]);  
        }  
        return ump.begin()->first;     
    }
};

Single Number ii

Given an array of integers, every element appears three times except for one. Find that single one.
参阅:http://bangbingsyb.blogspot.com/2014/11/leetcode-single-number-i-ii.html
这道题目给出的是其它数字出现3次
常规解法:用map统计次数，返回只有一次的数，速度很慢

解法1;

1110
1110
1110
1001
___
4331 对每一位进行求和
1001 对每一位的和做%3运算，来消去所有重复3次的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int singleNumber(int* nums, int numsSize) {
    int res = 0;
    //注意此处从高位开始
    for(int i = 31; i >= 0; i--){
        
        int sum = 0;
        int mask = 1<<i;
        
        for(int j = 0; j < numsSize; j++){
            if(nums[j] & mask)
                sum++;
        }
        res = (res<<1) + (sum%3);
    }
    return res;
}

简化后的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int singleNumber(int* nums, int numsSize) {
    int res = 0;
    for(int i = 0; i< 32; i++){
        int bitSum = 0;
        int bit = 1<<i;
        
        for(int j = 0; j < numsSize; j++)
            if(nums[j] & bit)
                bitSum++;
                
        if(bitSum % 3)  res |= bit;
    }
    return res;
}

解法2:掩码清零法
仅供参考，太难，重点掌握解法1；
参考:
http://www.acmerblog.com/leetcode-single-number-ii-5394.html
one 代表第ith 位只出现一次的掩码变量
two 代表第ith 位只出现两次次的掩码变量
three 代表第ith 位只出现三次的掩码变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int singleNumber(int* nums, int numsSize) {
    int one = 0, two =0, three = 0;
    
    for(int i = 0; i < numsSize; i++){
        //出现三次的数经过下面三次变换，为0
        two = one&nums[i];
        one ^= nums[i];
        three = one&two;
        
        one &= ~(three);
        two &= ~(three);
    }
    return one;
}

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
解题思路:取这个数组xor结果，结果肯定不为0，因为有两个数不一样，故可以找到这个不同的位，说明这两个数在此位上一个为0，一个为1，遍历一遍数组，将此位上为1的数xor，那么最终的结果为要求的一个数，将此位上为0的数xor，那么最终的结果为要求的另一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ret(2, 0);
        
        int xor_res = 0;
        for(int i = 0; i < nums.size(); i++)
            xor_res ^= nums[i];
        
        int pos = 0;    
        for(int i = 0; i < 32; i++){
            if(xor_res & 1<<i){
                pos = i;
                break;
            }
        }
        
        for(int i= 0; i < nums.size(); i++){
            if(nums[i] & 1<<pos)
                ret[0] ^= nums[i];
            else
                ret[1] ^= nums[i];
        }
        
        return ret;
    }
};